﻿//1283. 使结果不超过阈值的最小除数
//给你一个整数数组 nums 和一个正整数 threshold  ，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和。
//请你找出能够使上述结果小于等于阈值 threshold 的除数中 最小 的那个。
//每个数除以除数后都向上取整，比方说 7 / 3 = 3 ， 10 / 2 = 5 。
//题目保证一定有解。


class Solution {
public:
    bool check(vector<int>& nums, int threshold, int n)
    {
        int sum = 0;
        for (auto x : nums)
        {
            sum += (x + n - 1) / n;
            if (sum > threshold)
                return false;
        }
        return true;
    }
    int smallestDivisor(vector<int>& nums, int threshold)
    {
        int left = 1, right = ranges::max(nums);
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (check(nums, threshold, mid))
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        return right + 1;
    }
};